package org.example.leetCode;

import java.util.HashMap;
import java.util.Map;

/**
 * @author Administrator
 */
public class CopyRandomList {
    public Node copyRandomList(Node head) {
        if (head == null) {
            return head;
        }
        for (Node cur = head, copy = null; cur != null; cur = cur.next.next) {
            copy = new Node(cur.val);
            copy.next = cur.next;
            cur.next = copy;
        }

        for (Node cur = head; cur != null; cur = cur.next.next) {
            if (cur.random != null) {
                cur.next.random = cur.random.next;
            }
        }
        Node newHead = head.next;

        for (Node cur = head, temp = null; cur != null && cur.next != null; ) {
            temp = cur.next;
            cur.next = temp.next;
            cur = temp;
        }

        return newHead;


        //        if (head == null) {
//            return null;
//        }
//        Map<Node, Node> map = new HashMap<>();
//        for (Node node = head; node != null; node = node.next) {
//            map.put(node, new Node(node.val));
//        }
//
//        for (Node node = head; node != null; node = node.next) {
//            map.get(node).next = map.get(node.next);
//            map.get(node).random = map.get(node.random);
//        }
//        return map.get(head);
    }


    class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }
}
